package com.it.algprithm;

import java.util.Arrays;

/**
 * 目标： 掌握 二分查找
 * 前提条件： 数组中的数据必须是有序
 * 核心思想：每次排除一半数据，查询数据的性能明显提高很多
 * 结论：二分查找正常的折半条件应该是开始位置left<=结束位置right
 */
public class Test3 {
    public static void main(String[] args) {
        // 1. 准备好一个数组
        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};

        System.out.println(binarySearch(arr, 81));

        //  java的Arrays类提供了二分查找方法：binarySearch()方法，
        System.out.println(Arrays.binarySearch(arr,131));
    }

    //    形参=> 参数1：数组（int[] arr）; 参数2：要查找的数据（int data)
    public static int binarySearch(int[] arr, int data) {
        // 1.定义两个变量，一个站在左边位置，一个站在右边位置
        int left = 0; // 索引
        int right = arr.length - 1; // 索引

        // 2.定义一个循环控制折半
        while (left <= right) {
            // 3.每次折半，都算出中间位置处的索引
            int middle = (left + right) / 2;
            // 4.判断当前要找的元素值，与中间位置处的元素值的大小情况
            if (data < arr[middle]) {
                // 往左边找，截止位置（右边位置） = 中间位置 - 1
                right = middle - 1;
            } else if (data > arr[middle]) {
                // 往右边找，起始位置（左边位置） = 中间位置 + 1
                left = middle + 1;
            } else {
                // 中间位置处的元素值，正好等于我们要找的元素值
                return middle;
            }
        }
        return -1; // -1 特殊结果，就代表没有找到数据！数组中不存在该数据
    }
}
